// synch.cc 
//	Routines for synchronizing threads.  Three kinds of
//	synchronization routines are defined here: semaphores, locks 
//   	and condition variables (the implementation of the last two
//	are left to the reader).
//
// Any implementation of a synchronization routine needs some
// primitive atomic operation.  We assume Nachos is running on
// a uniprocessor, and thus atomicity can be provided by
// turning off interrupts.  While interrupts are disabled, no
// context switch can occur, and thus the current thread is guaranteed
// to hold the CPU throughout, until interrupts are reenabled.
//
// Because some of these routines might be called with interrupts
// already disabled (Semaphore::V for one), instead of turning
// on interrupts at the end of the atomic operation, we always simply
// re-set the interrupt state back to its original value (whether
// that be disabled or enabled).
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved.  See copyright.h for copyright notice and limitation 
// of liability and disclaimer of warranty provisions.

#include "copyright.h"
#include "synch.h"
#include "system.h"

//----------------------------------------------------------------------
// Semaphore::Semaphore
// 	Initialize a semaphore, so that it can be used for synchronization.
//
//	"debugName" is an arbitrary name, useful for debugging.
//	"initialValue" is the initial value of the semaphore.
//----------------------------------------------------------------------

Semaphore::Semaphore(char* debugName, int initialValue)
{
    name = debugName;
    value = initialValue;
    queue = new List;
}

//----------------------------------------------------------------------
// Semaphore::Semaphore
// 	De-allocate semaphore, when no longer needed.  Assume no one
//	is still waiting on the semaphore!
//----------------------------------------------------------------------

Semaphore::~Semaphore()
{
    delete queue;
}

//----------------------------------------------------------------------
// Semaphore::P
// 	Wait until semaphore value > 0, then decrement.  Checking the
//	value and decrementing must be done atomically, so we
//	need to disable interrupts before checking the value.
//
//	Note that Thread::Sleep assumes that interrupts are disabled
//	when it is called.
//----------------------------------------------------------------------

void
Semaphore::P()
{
    IntStatus oldLevel = interrupt->SetLevel(IntOff);	// disable interrupts
    
    while (value == 0) { 			// semaphore not available
	queue->Append((void *)currentThread);	// so go to sleep
	currentThread->Sleep();
    } 
    value--; 					// semaphore available, 
						// consume its value
    
    (void) interrupt->SetLevel(oldLevel);	// re-enable interrupts
}

//----------------------------------------------------------------------
// Semaphore::V
// 	Increment semaphore value, waking up a waiter if necessary.
//	As with P(), this operation must be atomic, so we need to disable
//	interrupts.  Scheduler::ReadyToRun() assumes that threads
//	are disabled when it is called.
//----------------------------------------------------------------------

void
Semaphore::V()
{
    Thread *thread;
    IntStatus oldLevel = interrupt->SetLevel(IntOff);

    thread = (Thread *)queue->Remove();
    if (thread != NULL)	   // make thread ready, consuming the V immediately
	scheduler->ReadyToRun(thread);
    value++;
    (void) interrupt->SetLevel(oldLevel);
}

// Dummy functions -- so we can compile our later assignments 
// Note -- without a correct implementation of Condition::Wait(), 
// the test case in the network assignment won't work!
//----------------------------------------------------------------------
// 	Lock::Lock
// 	Initialize a lock, so that it can be used for synchronization.
//	the lock is initialized to be FREE
//	"debugName" is an arbitrary name, useful for debugging.
//----------------------------------------------------------------------
Lock::Lock(char* debugName) {
	name = debugName;
	lockHolder = NULL;
	queue = new List;
	value = FREE;
}

//----------------------------------------------------------------------
// Lock::~Lock
// 	De-allocate lock, when no longer needed.  Assume no one
//	is still waiting on the lock!
//----------------------------------------------------------------------
Lock::~Lock() {
	delete queue;
}

//----------------------------------------------------------------------
// Lock::Acquire()
//	wait until the lock is FREE, then set it to BUSY
//----------------------------------------------------------------------
void Lock::Acquire() {
	IntStatus oldLevel = interrupt->SetLevel(IntOff); // disable interrupts

	while (value == BUSY) { // lock is held by some thead
			queue->Append((void *) currentThread); // so go to sleep
			currentThread->Sleep();
		}
	value = BUSY; // hold the lock
	lockHolder = currentThread;

	(void) interrupt->SetLevel(oldLevel); // re-enable interrupts
}
//----------------------------------------------------------------------
// Lock::Release()
// 	set lock to be FREE, waking up a thread waiting
//	on the lock(if there are any)
//----------------------------------------------------------------------
void Lock::Release() {
	if (isHeldByCurrentThread()) { // only the thread that acquired the lock can release it.
		value=FREE;				//set the lock free
		lockHolder = NULL;
		Thread *thread;
		IntStatus oldLevel = interrupt->SetLevel(IntOff); // disable interrupts
		thread = (Thread *) queue->Remove();
		if (thread != NULL){ // make thread ready,
			scheduler->ReadyToRun(thread);
		}
		(void) interrupt->SetLevel(oldLevel);  // re-enable interrupts
	}
}
//----------------------------------------------------------------------
// Lock::isHeldByCurrentThread()
// return true if the current thread holds this lock.
//----------------------------------------------------------------------
bool Lock::isHeldByCurrentThread(){
	return lockHolder == currentThread;
}
//----------------------------------------------------------------------
// Condition::Condition
//initialize condition to
// "no one waiting"
//----------------------------------------------------------------------
Condition::Condition(char* debugName) {
	this->name = debugName;
	queue = new List();
	lock = NULL;
}
//----------------------------------------------------------------------
// Condition::~Condition
//deallocate the condition
//----------------------------------------------------------------------
Condition::~Condition() {
	delete queue;

}
//----------------------------------------------------------------------
// Condition:Wait
// these are the 3 operations on
// condition variables; releasing the
// lock and going to sleep are
// *atomic* in Wait()
//----------------------------------------------------------------------
void Condition::Wait(Lock* conditionLock) {
	if(lock!=NULL&&lock!=conditionLock){
		printf("The condition variable can't be used by two locks!");
		return;
	}
	else
		lock = conditionLock;
	queue->Append(currentThread);
	IntStatus oldLevel = interrupt->SetLevel(IntOff);
	conditionLock->Release();
	currentThread->Sleep();
	(void) interrupt->SetLevel(oldLevel);
	conditionLock->Acquire();
	}

void Condition::Signal(Lock* conditionLock) {
	IntStatus oldLevel = interrupt->SetLevel(IntOff);
	Thread* thread = (Thread*)queue->Remove();
	if(thread!=NULL)
		scheduler->ReadyToRun(thread);
	(void) interrupt->SetLevel(oldLevel);
	conditionLock->Release();
	conditionLock->Acquire();
}
void Condition::Broadcast(Lock* conditionLock) {
	Thread* thread;
	IntStatus oldLevel = interrupt->SetLevel(IntOff);
	while(!queue->IsEmpty()){
		thread = (Thread*)queue->Remove();
		if(thread!=NULL)
			scheduler->ReadyToRun(thread);
	}
	(void) interrupt->SetLevel(oldLevel);
	conditionLock->Release();
	conditionLock->Acquire();
}
#if defined(CHANGED) && defined(THREADS)
Barrier::Barrier(int n){
	this->goal = n;
	this->queue = new List;
	this->number = 0;
}
Barrier::~Barrier(){
	delete queue;
}
void Barrier::wait(){
	 IntStatus oldLevel = interrupt->SetLevel(IntOff);	// disable interrupts
		number++;
	    if (number != goal) { 			// semaphore not available
		queue->Append((void *)currentThread);	// so go to sleep
		currentThread->Sleep();
	    }
	    Thread* thread = (Thread *)queue->Remove();
	    if (thread != NULL)	   // make thread ready, consuming the V immediately
	   	{scheduler->ReadyToRun(thread);
	   	}
	    if(queue->IsEmpty())
	    	number = 0;
	    (void) interrupt->SetLevel(oldLevel);	// re-enable interrupts
}
#endif
